1. Field of the Invention
This invention relates to method and apparatus for constructing a 3D polygonal surface from a 2D silhouette by using computer. This invention relates to method and system for providing a sketching interface for 3D freeform design.
2. Description of the Related Art
A typical procedure for geometric modeling is to start with a simple primitive such as a cube or a sphere, and gradually construct a more complex model through successive transformations or a combination of multiple primitives. Various deformation techniques (R. MacCracken and K. I. Joy. Free-form deformations with lattices of arbitrary topology. SIGGRAPH 96 Conference Proceedings, pages 181-188, 1996.)(K. Singh and E. Fiume. Wires: a geometric deformation technique. SIGGRAPH 98 Conference Proceedings, pages 405-414, 1998.) and other shape-manipulation tools (C. Grimm, D. Pugmire, M. Bloomental, J. F. Hughes, and E. Cohen. Visual interfaces for solids modeling. UIST ""95 Conference Proceedings, pages 51-60, 1995.) are examples of transformation techniques that let the user create a wide variety of precise, smooth shapes by interactively manipulating control points or 3D widgets.
Another approach to geometric modeling is the use of implicit surfaces (J. Bloomenthal and B. Wyvill. Interactive techniques for implicit modeling. 1990 Symposium on Interactive 3D Graphics, pages 109-116, 1990.)(L. Markosian, J. M. Cohen, T. Crulli and J. F. Hughes. Skin: A Constructive Approach to Modeling Free-form Shapes. SIGGRAPH 99, to appear, 1999.) The user specifies the skeleton of the intended model and the system constructs smooth, natural-looking surfaces around it. The surface inflation technique (H. Nishimura, M. Hirai, T. Kawai, T. Kawata, I. Shirakawa, K. Omura. Object modeling by distribution function and a method of image generation. Transactions of the Institute of Electronics and Communication Engineers of Japan, J68-D(4):718-725, 1985) extrudes the polygonal mesh from the skeleton outwards. In contrast, the user can also specify the silhouette of the intended shape directly instead of by specifying its skeleton.
Some modeling systems achieve intuitive, efficient operation using 3D input/output devices (M. Deering. The Holosketch VR sketching system. Communications of the ACM, 39(5):54-61, May 1996.). 3D devices can simplify the operations that require multiple operations when using 2D devices.
Known sketch-based modeling systems are L. Eggli, C. Hsu, G. Elber, and B. Bruderlin, Inferring 3D models from freehand sketches and constraints. Computer-Aided Design, 29(2): 101-112, February 1997. and R. C. Zeleznik, K. P. Herndon, and J. F. Hughes. SKETCH: An interface for sketching 3D scenes. SIGGRAPH 96 Confetence Proceedings, pages 163-170, 1996. They interpret the user""s freeform strokes and interactively construct 3D rectilinear models. It is an aim to develop a similar interface for designing rounded freeform models.
Inflation of a 2D drawing is introduced in L. Williams. Shading in Two Dimensions. Graphics Interface ""91, pages 143-151, 1991, and 3D surface editing based on a 2D painting technique is discussed in L. Williams. 3D Paint. 1990 Symposium on Interactive 3D Graphics, pages 225-233, 1990.
Their target is basically a 2D array with associated height values, rather than a 3D polygonal model.
The use of freeform strokes for 2D applications has recently become popular. Some systems (M. D. Gross and E. Y. L. Do. Ambiguous intentions: A paper-like interface for creative design. UIST""96 Conference Proceedings, pages 183-192, 1996.)(J. A. Landay and B. A. Myers. Interactive sketching for the early stages of user interface design. CHI""95 Conference Proceedings, pages 43-50, 1995.) use strokes to specify gestural commands and others (T. Baudel. A mark-based interaction paradigm for free-hand drawing. UIST""94 Conference Proceedings, pages 185-192, 1994.) use freeform strokes for specifying 2D curves. These systems find the best matching arcs or splines automatically, freeing the users from explicit control of underlying parameters.
Some systems use a volumetric representation (T. Galyean and J. F. Hughes. Sculpting: an interactive volumetric modeling technique. SIGGRAPH ""91 Conference Proceedings, pages 267-274, 1991.)(S. W. Wang and A. E. Kaufman, volume sculpting. 1995 Symposium on Interactive 3D Graphics, pages 109-116, 1995.), which is useful for designing topologically complicated shapes. The mesh-construction algorithm according to the present invention is based on a variety of work on polygonal mesh manipulation, such as mesh optimization (H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. SIGGRAPH 93 Conference Proceedings, pages 19-26, 1993.), shape design (W. Welch and A. Witkin. Free-form shape design using triangulated surfaces. SIGGRAPH 94 Conference Proceedings, pages 247-256, 1994.), and surface fairing (G. Taubin. A signal processing approach to fair surface design. SIGGRAPH 95 Conference Proceedings, pages 351-358, 1995.), which allows polygonal meshes to be widely used as a fundamental representation for geometric modeling and computer graphics in general.
Although much progress has been made over the years on 3D modeling systems, they are still difficult and tedious to use when creating freeform surfaces. Their emphasis has been the precise modeling of objects motivated by CAD and similar domains. Recently SKETCH (R. C. Zeleznik, K. P. Herndon, and J. F. Hughes. SKETCH: An interface for sketching 3D scenes. SIGGRAPH 96 Conference Proceedings, pages 163-170, 1996.) introduced a gesture-based interface for the rapid modeling of CSG-like models consisting of simple primitives.
The present invention extends these ideas to create a sketching interface for designing 3D freeform objects. The essential idea is the use of freeform strokes as an expressive design tool. The user draws 2D freeform strokes interactively specifying the silhouette of an object, and the system automatically constructs a 3D polygonal surface model based on the strokes. The user does not have to manipulate control points or combine complicated editing operations. Using this technique, even first-time users can create simple, yet expressive 3D models within minutes. In addition, the resulting models have a hand-crafted feel (such as sculptures and stuffed animals) which is difficult to accomplish with most conventional modelers.
The present invention is method for constructing a 3D polygonal surface from a 2D silhouette by using computer, comprising the steps of: creating a new closed polygonal mesh model from an initial stroke; determining the spine of the polygon using the chordal axis; elevating vertices of said spine by an amount proportional to their distance from the polygon; constructing a polygonal mesh by wrapping said spine and said polygon in such a way that sections form ovals.
The present invention is apparatus for constructing a 3D polygonal surface from a 2D silhouette, comprising: a first section for creating a new closed polygonal mesh model from an initial stroke; a second section for determining the spine of the polygon using the chordal axis; a third section for elevating vertices of said spine by an amount proportional to their distance from the polygon; a forth section for constructing a polygonal mesh by wrapping said spine and said polygon in such a way that sections form ovals.
The present invention is a medium recording a program for constructing a 3D polygonal surface from a 2D silhouette, which creates a new closed polygonal mesh model from an initial stroke; determines the spine of the polygon using the chordal axis; elevates vertices of said spine by an amount proportional to their distance from the polygon; constructs a polygonal mesh by wrapping said spine and said polygon in such a way that sections form ovals.
Medium includes, for example, a floppy disk, a hard disk, a magnetic tape, a magneto optical disk, a CD-ROM, a DVD, a ROM cartridge, a RAM memory cartridge with a backup battery, a flash memory cartridge and a non-volatile RAM cartridge.
Medium also includes such wire communication medium as telephone lines, and such wireless communication medium as microwave lines. Internet is also included in the communication medium mentioned here.
Medium is a material substance where information (mainly digital data, programs) have been recorded by some physical means, so that such a processing device as a dedicated processor can execute predetermined functions. A medium is for downloading programs to a computer and having the computer execute predetermined functions by some means.